package com.isaiah.algorithms.sort;

import com.isaiah.util.FileUtil;

import java.util.Arrays;
import java.util.List;

/**
 * @Title: 希尔排序
 * @Description:
 * @author: Haijun
 * @emial: isaiah@sohu.com
 * @date 2021/10/2610:29
 */
public class ShellSort {
    public static <T>  void sort(Comparable<T>[] arr){
        //确定增长量h的最大值
        final int  N = arr.length;
        int h = 1;
        while (h < N / 2){
            h = h * 2 + 1;

        }

        System.out.println("计算出增长量h为：" + h);



        //当增长量h小于1，排序结束，  最外层循环每一趟
        while(h >= 1){
            //从h位置到数组绷带位置找到待插入的元素
            for (int i =h; i < N; i++){
                // 第一个待插入的数组，其实就是h索引处理的元素， 第二个就是h+1
                for (int j = i; j >= h; j-= h){
                    if (greater(arr[j-h], arr[j])){
                        swap(arr, j, j-h);

                    }else{
                        break;
                    }
                }
            }
            // 让h以它的一半缩小范围
            h /= 2;
        }

    }
    /**
     * 判断a是否大于b
     * @param a
     * @param b
     * @param <T>
     * @return
     */
    private static <T> boolean greater(Comparable<T> a, Comparable<T> b){
        return a.compareTo((T) b) > 0;
    }

    /**
     * 交换数组arr的i索引与j索引上的元素
     * @param arr
     * @param i
     * @param j
     * @param <T>
     */
    private static <T> void  swap(Comparable<T>[] arr, int i, int j){
        Comparable<T> temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

    }


    public static void main(String[] args) {
        List<Integer> list = FileUtil.readLine();
        Integer[] arr = list.toArray(new Integer[list.size()]);
        testInsertion(arr);
        System.out.println(Arrays.toString(arr));

        testShell(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static int getGrap(int length){
        int N = length;
        int h = 1;
        while (h<N/2){
            // 让h始终以奇数增长
            h = h*2+1;
        }
        return h;
    }

    public static void testShell(Integer[] arr){
        long start = System.currentTimeMillis();
        ShellSort.sort(arr);
        long end = System.currentTimeMillis();
        System.out.println("shell排序执行的时间:" + (end-start));
    }
    public static void testInsertion(Integer[] arr){
        long start = System.currentTimeMillis();
        InsertionSort.sort(arr);
        long end = System.currentTimeMillis();
        System.out.println("Insertion排序执行的时间:" + (end-start));
    }
}
